package com.demo.v5;

public class RbTree<T extends Comparable<T>> {
    /**
     * 根节点
     */
    private RbtNode<T> mRoot;

    /**
     * 查找红黑树中指定为key的节点
     */
    public RbtNode<T> search(T key) throws Exception {
        return search(mRoot, key);
    }

    private RbtNode<T> search(RbtNode<T> x, T key) throws Exception {
        if(x == null){
            throw new Exception("key can't null");
        }
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            return search(x.right, key);
        }else if(cmp < 0){
            return search(x.left, key);
        }else{
            return x;
        }
    }

    /**
     * 插入key值到红黑树
     */
    public void insert(T key) throws Exception {
        //1. 构建黑色节点并检验空值
        RbtNode<T> node = generateBlackNodeByKey(key);
        //2. 将红黑树当作二叉查找树，节点添加到二叉查找树中，设置节点颜色为红色
        insertNodeInUnbalanceTree(node);
        //3. 按照红黑规则调整为红黑树
        balanceTreeByInsertNode(node);
    }

    /**
     * 构建黑色节点并检验空值
     * @param key
     * @return
     * @throws Exception
     */
    private RbtNode<T> generateBlackNodeByKey(T key) throws Exception {
        if(key != null){
            return new RbtNode<T>(key, RbtNode.BLACK, null, null, null);
        }else{
            //抛出异常进行测试，不建议返回null
            throw new Exception("key can't null");
        }
    }

    /**
     * 将红黑树当作二叉查找树，节点添加到二叉查找树中，设置节点颜色为红色
     */
    private void insertNodeInUnbalanceTree(RbtNode<T> node){
        //1. 获取需要插入子节点的父节点
        RbtNode<T> parentNode = getNodeItNeedAddChild(node);
        //2. 在父节点下插入子节点
        insertNodeByOnParentNode(node, parentNode);
        //3. 调整插入子节点颜色为红
        node.color = RbtNode.RED;
    }

    private void insertNodeByOnParentNode(RbtNode<T> node, RbtNode<T> parentNode){
        node.parent = parentNode;
        if (parentNode != null) {
            int cmp = node.key.compareTo(parentNode.key);
            if (cmp < 0){
                parentNode.left = node;
            } else {
                parentNode.right = node;
            }
        } else {
            this.mRoot = node;
        }
    }

    private RbtNode<T> getNodeItNeedAddChild(RbtNode<T> node){
        RbtNode<T> tempNode = null;
        RbtNode<T> tempRootNode = this.mRoot;
        while (tempRootNode != null) {
            tempNode = tempRootNode;
            int cmp = node.key.compareTo(tempRootNode.key);
            if (cmp < 0){
                tempRootNode = tempRootNode.left;
            } else {
                tempRootNode = tempRootNode.right;
            }
        }
        return tempNode;
    }

    /**
     * 按照红黑规则调整为红黑树
     * @param node
     */
    private void balanceTreeByInsertNode(RbtNode<T> node){
        //TODO wangshengkai
        //TODO 根据红黑规则,考虑需要左旋,右旋,判断节点红黑,获取父节点,获取节点颜色方法
    }

    /**
     * 打印红黑树
     */
    public void print(){
        //TODO wangshengkai
    }

    /**
     * 红黑树节点左旋
     * @param x
     */
    private void leftRotate(RbtNode<T> x) {
        RbtNode<T> y = x.right;
        x.right = y.left;
        if (y.left != null){
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.mRoot = y;
        } else {
            if (x.parent.left == x){
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        }
        y.left = x;
        x.parent = y;
    }

    /**
     * 红黑树节点右旋
     * @param y
     */
    private void rightRotate(RbtNode<T> y) {
        RbtNode<T> x = y.left;
        y.left = x.right;
        if (x.right != null){
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == null) {
            this.mRoot = x;
        } else {
            if (y == y.parent.right){
                y.parent.right = x;
            } else {
                y.parent.left = x;
            }
        }
        x.right = y;
        y.parent = x;
    }

    private RbtNode<T> parentOf(RbtNode<T> node) {
        return node != null ? node.parent : null;
    }

    private boolean colorOf(RbtNode<T> node) {
        return node != null ? node.color : RbtNode.BLACK;
    }

    private boolean isRed(RbtNode<T> node) {
        return ((node != null) && (node.color == RbtNode.RED)) ? true : false;
    }

    private boolean isBlack(RbtNode<T> node) {
        return !isRed(node);
    }

    private void setBlack(RbtNode<T> node) {
        if (node != null){
            node.color = RbtNode.BLACK;
        }
    }

    private void setRed(RbtNode<T> node) {
        if (node != null){
            node.color = RbtNode.RED;
        }
    }

    private void setParent(RbtNode<T> node, RbtNode<T> parent) {
        if (node != null){
            node.parent = parent;
        }
    }

    private void setColor(RbtNode<T> node, boolean color) {
        if (node != null){
            node.color = color;
        }
    }
}
